package com.linyaonan.leetcode.medium._739;

import java.util.LinkedList;

/**
 * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: temperatures = [73,74,75,71,69,72,76,73]
 * 输出: [1,1,4,2,1,1,0,0]
 * 示例 2:
 * <p>
 * 输入: temperatures = [30,40,50,60]
 * 输出: [1,1,1,0]
 * 示例 3:
 * <p>
 * 输入: temperatures = [30,60,90]
 * 输出: [1,1,0]
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= temperatures.length <= 10^5
 * 30 <= temperatures[i] <= 100
 *
 * @author: Lin
 * @date: 2024/3/14
 */
public class DailyTemperatures {

    /**
     * 按照这个数据+单调栈分析过程73,74,75,71,69,72,76,73
     * stack: [73]
     * index:[0]
     * result []
     * <p>
     * stack:[73] <=74  => [74]
     * index:[1]
     * result:[1]
     * <p>
     * stack:[74] <=75  => [75]
     * index:[2]
     * result:[1,1]
     * <p>
     * stack:[75] <=71  => [75,71]
     * index:[2,3]
     * result:[1,1,null]
     * <p>
     * stack:[75.71] <=69 => [75,71,69]
     * index:[2,3,4]
     * result:[1,1,null,null]
     * <p>
     * stack:[75,71,69] <=72 => [75,72]
     * index:[2,5]
     * result:[1,1,null,2,1]
     * <p>
     * stack:[75,72] <=76 => [76]
     * result:[]
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        // 异常边界
        if (temperatures.length == 1) {
            return new int[]{0};
        }
        int[] r = new int[temperatures.length];
        // 使用单调栈处理
        // 用于保存数值以及比较
        LinkedList<Integer> vStack = new LinkedList<>();
        // 只用于存储数值对应的索引
        LinkedList<Integer> iStack = new LinkedList<>();

        vStack.addLast(temperatures[0]);
        iStack.addLast(0);


        for (int i = 1; i < temperatures.length; i++) {
            boolean cc = true;
            int add = temperatures[i];
            while (cc && !vStack.isEmpty()) {
                Integer topValue = vStack.getLast();
                Integer topIndex = iStack.getLast();
                // 表示找到第一个比目标值大的value
                if (add > topValue) {
                    r[topIndex] = i - topIndex;
                    vStack.removeLast();
                    iStack.removeLast();
                    cc = true;
                } else {
                    cc = false;
                }
            }
            vStack.addLast(add);
            iStack.addLast(i);

        }

        return r;

    }

    /**
     * 单调栈思路，如果遇到比栈顶部的数值大的，就可以弹出栈的数据，依次弹出直到比栈顶数据小
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures2(int[] temperatures) {
        // 1. 特殊情况
        if (temperatures.length == 1) {
            return new int[]{0};
        }
        int[] result = new int[temperatures.length];
        LinkedList<Integer> list = new LinkedList<>();
        // 用来记录没有填充数值的索引
        LinkedList<Integer> index = new LinkedList<>();

        for (int i = 0; i < temperatures.length; i++) {
            if (list.isEmpty()) {
                list.addLast(temperatures[i]);
                index.addLast(i);
            } else {
                int add = temperatures[i];
                if (list.peekLast() < add) {
                    while (!list.isEmpty() && list.peekLast() < add) {
                        Integer lastIndex = index.removeLast();
                        result[lastIndex] = i - lastIndex;
                        list.removeLast();
                    }
                }
                index.addLast(i);
                list.addLast(add);
            }
        }
        result[temperatures.length - 1] = 0;

        return result;

    }

}
